package cn.lishiyuan.algorithm.sort;

import java.util.List;

/**
 * 希尔排序
 * <br>
 * 希尔排序是插入排序的改进。
 * <br>
 * 希尔排序的思路是选择不一样的步长策略将原本的插入排序变成多阶段的不同步长的插入排序。
 * 比如：13，4，1。到步长递减为为1的时候便是常规的插入排序。
 *
 */
public class ShellSort implements LeeSort{

    @Override
    public <T extends Comparable<T>> List<T> sort(List<T> data) {

        // Knuth 序列步长选择策略
        int step = 1;
        int length = data.size();
        while (step < (length / 3)) {
            // 1,4,13,40
            step = (step * 3) + 1;
        }

        for (;step >= 1 ;step = ((step -1) / 3) ) {

            for (int i = step; i < length; i++) {
                // 将当前元素插入到合适的index
                T temp = data.get(i);

                // 找出前方合适的index
                int j = i;
                for (;j >= step; j-=step) {
                    T left = data.get( j-step );
                    // 如果当前元素大于需要插入的元素则表示直接放到当前位置就行
                    if (temp.compareTo(left) > 0) {
                        break;
                    }
                    // 如果当前元素不大于需要插入的元素则向后移动给需要插入的index腾出空间。
                    data.set(j, data.get(j - step));
                }
                data.set(j, temp);
            }

        }
        return data;
    }



    @Override
    public <T extends Comparable<T>> T[] sort(T[] data) {
        // Knuth 序列步长选择策略
        int step = 1;
        int length = data.length;
        while (step < (length / 3)) {
            // 1,4,13,40
            step = (step * 3) + 1;
        }

        for (;step >= 1 ;step = ((step -1) / 3) ) {

            for (int i = step; i < length; i++) {
                // 将当前元素插入到合适的index
                T temp = data[i];

                // 找出前方合适的index
                int j = i;
                for (;j >= step; j-=step) {
                    T left = data[j-step];
                    // 如果当前元素大于需要插入的元素则表示直接放到当前位置就行
                    if (temp.compareTo(left) > 0) {
                        break;
                    }
                    // 如果当前元素不大于需要插入的元素则向后移动给需要插入的index腾出空间。
                    data[j] = data[j - step];
                }
                data[j] = temp;
            }

        }
        return data;
    }
}
